This invention relates to compilation of electronic designs. More specifically, it relates to methods, machine readable media, and apparatuses for rapidly compiling electronic designs via parallel processing.
Electronic design automation ("EDA") is becoming increasingly complicated and time consuming, due in part to the greatly increasing size and complexity of the electronic devices designed by EDA tools. Such devices include general purpose microprocessors as well as custom logic devices including Application Specific Integrated Circuits ("ASICs"). Examples of ASICs include non-programmable gate arrays, field programmable gate arrays ("FPGAs"), and complex programmable logic devices ("PLDs" or "CPLDs"). The design of even the simplest of these devices typically involves generation of a high level design, logic simulation, generation of a network, timing simulation, etc. Usually, timing simulation cannot be performed until the design has been compiled to the point where the various gate level entities are synthesized and placed and the lines therebetween routed on a target hardware device. This compilation requires that a design project (or a significant piece of it) be functionally completed.
Meeting timing requirements is essential to the correct operation of an integrated circuit. For example, for a plurality of D-type flip-flops ("DFFs") to feed through some logic to another plurality of DFFs, it is generally required that the signals form the first set of DFFs must finish propagating through any intermediate logic and have settled to their final state on the D-input of each of the destination DFFs before the next rising edge of the clock. (In fact they must finish before the next clock edge by an amount known as the setup delay of the register T.sub.su.) If the delay through the resulting logic is greater than the time between rising clock edges, then the state that the destination DFFs will hold on the next clock edge will be undefined.
Quite typically, a designer (or the compiler itself) will modify a design after an initial compilation. This may be required when a timing simulation conducted after compilation indicates a problem. Or, the product requirements may change in the middle of the device's development. Regardless of why a design change is necessary, that change requires a recompile. Unfortunately, each compilation consumes significant time, so multiple recompiles translates to significantly longer development times. This can greatly slow the time to market for an integrated circuit under design. Because PLDs rely on a short time to market as a major selling point, slow development can erase any commercial advantage.
The problem is compounded because maximum CPLD device sizes are increasing at a speed slightly greater than that predicted by Moore's law (i.e., each new chip contains roughly twice as much capacity as its predecessor, and each chip is released within 18-24 months of the previous chip). If compilation time was a linear function of design size then it would be expected that the time to compile the largest device on the most powerful computer would remain approximately constant. Unfortunately, compile times are typically proportional to n.sup.2, where n is the number of logic elements on a device. This means that a design twice as big takes four times as long to compile. Consequently, the compile times for the largest devices are accelerating. It is not uncommon for large projects to compile for about 24 hours or more on a modern workstation. Obviously, the fastest compilers will become critical components of integrated circuit design environments.
Large designs often benefit from performing and comparing multiple compilations, each based upon a different compilation parameters or slight design changes. For example, the heuristics for synthesizing and/or the heuristics for mapping a design can be varied to emphasize different goals (e.g., speed versus compact fit). Obviously, given long compile times, most designers do not have the luxury of running multiple compilations for comparison.
An important advance in the effort to reduce compilation time for large devices is incremental compilation. In essence, incremental compilation involves using a previously compiled design such that only a fraction of that design must be recompiled after a user or compiler makes one or more changes to the design. Incremental compilation requires at least two steps: (1) delineating a sphere of influence of user changes in a previously compiled design (the sphere of influence typically being defined within a netlist), and (2) recompiling the logic from within this sphere of influence into appropriate logic elements available within a target hardware device. To maximize efficiency, the compiler should limit recompile to a minimum region of the electronic design (and a corresponding region of a target hardware device) which is directly affected by the design change.
One suitable technique for delineating a sphere of influence of user changes to a previously compiled design (step 1) involves a "netlist differencing" method in conjunction with a "sub-netlist" identification method. Given a change to a design, the compiler can re-extract the netlist, run netlist differencing on the netlist to identify which nodes and/or nets have actually changed. Netlist differencing is described in U.S. patent application Ser. No. 08/619,073, filed on Mar. 20, 1996, naming Lee as inventor and entitled "METHODS FOR IMPLEMENTING CIRCUIT DESIGNS IN PHYSICAL CIRCUITS." Because the effects of the user's changes propagate beyond those nodes/nets that were actually changed, the compiler uses an appropriate technique for expanding the changed portion of the design beyond the design entities identified by netlist differencing. One suitable technique for identifying the sphere of influence of the changes is the sub-netlist method as described in U.S. patent application Ser. No. 08/958,002, filed on the same day as the instant patent application, naming B. Pedersen et al. as inventors and entitled "GENERATION OF SUB-NET LISTS FOR USE IN INCREMENTAL COMPILATION." The now delineated changed portion of the design may resynthesized, remapped, and refit (step 2). A suitable technique for fitting changed cells is described in U.S. patent application Ser. No. 08/958,436, filed on the same day as the instant patent application, naming J. Tse et al. as inventors and entitled "FITTING FOR INCREMENTAL COMPILATION OF ELECTRONIC DESIGNS." All three of the above applications are incorporated herein by reference for all purposes.
While the above-described incremental compile techniques help reduce the time devoted to compiling designs, other techniques for decreasing compile time would be quite welcome.